In general, image processing is the analysis and manipulation of two-dimensional representations, which can comprise photographs, drawings, paintings, blueprints, x-rays of medical patients, or indeed abstract art or artistic patterns. These images are all two-dimensional arrays of information. Until fairly recently, images have comprised almost exclusively analog displays of analog information, for example, conventional photographs and motion pictures. Even the signals encoding television pictures, notwithstanding that the vertical scan comprises a finite number of lines, are fundamentally analog in nature.
Beginning in the early 1960's, images began to be captured or converted and stored as two-dimensional digital data, and digital image processing followed. At first, images were recorded or transmitted in analog form and then converted to digital representation for manipulation on a computer. Currently digital capture and transmission are on their way to dominance, in part because of the advent of charge coupled device (CCD) image recording arrays and in part because of the availability of inexpensive high speed computers to store and manipulate images.
An important task of image processing is the correction or enhancement of a particular image. For example, digital enhancement of images of celestial objects taken by space probes has provided substantial scientific information. However, the current invention relates primarily to compression for transmission or storage of digital images and not to enhancement.
One of the problems with digital images is that a complete single image frame can require up to several megabytes of storage space or transmission bandwidth. That is, one of today's 3½ inch floppy discs can hold at best a little more than one gray-scale frame and sometimes substantially less than one whole frame. A full-page color picture, for example, uncompressed, can occupy 30 megabytes of storage space. Storing or transmitting the vast amounts of data which would be required for real-time uncompressed high resolution digital video is technologically daunting and virtually impossible for many important communication channels, such as the telephone line. The transmission of digital images from space probes can take many hours or even days if insufficiently compressed images are involved. Accordingly, there has been a decades long effort to develop methods of extracting from images the information essential to an aesthetically pleasing or scientifically useful picture without degrading the image quality too much and especially without introducing unsightly or confusing artifacts into the image.
The basic approach has usually involved some form of coding of picture intensities coupled with quantization. One approach is block coding; another approach, mathematically equivalent with proper phasing, is multiphase filter banks. Frequency based multi-band transforms have long found application in image coding. For instance, the JPEG image compression standard, W. B. Pennebaker and J. L. Mitchell, “JPEG: Still Image Compression Standard,” Van Nostrand Reinhold, 1993, employs the 8×8 discrete cosine transform (DCT) at its transformation stage. At high bit rates, JPEG offers almost lossless reconstructed image quality. However, when more compression is needed, annoying blocking artifacts appear since the DCT bases are short and do not overlap, creating discontinuities at block boundaries.
The wavelet transform, on the other hand, with long, varying-length, and overlapping bases, has elegantly solved the blocking problem. However, the transform's computational complexity can be significantly higher than that of the DCT. This complexity gap is partly in terms of the number of arithmetical operations involved, but more importantly, in terms of the memory buffer space required. In particular, some implementations of the wavelet transform require many more operations per output coefficient as well as a large buffer.
An interesting alternative to wavelets is the lapped transform, e.g., H. S. Malvar, Signal Processing with Lapped Transforms, Artech House, 1992, where pixels from adjacent blocks are utilized in the calculation of transform coefficients for the working block. The lapped transforms outperform the DCT on two counts: (i) from the analysis viewpoint, they take into account inter-block correlation and hence provide better energy compaction; (ii) from the synthesis viewpoint, their overlapping basis functions decay asymptotically to zero at the ends, reducing blocking discontinuities dramatically.
Nevertheless, lapped transforms have not yet been able to supplant the unadorned DCT in international standard coding routines. The principal reason is that the modest improvement in coding performance available up to now has not been sufficient to justify the significant increase in computational complexity. In the prior art, therefore, lapped transforms remained too computationally complex for the benefits they provided. In particular, the previous lapped transformed somewhat reduced but did not eliminate the annoying blocking artifacts.
It is therefore an object of the current invention to provide a new transform which is simple and fast enough to replace the bare DCT in international standards, in particular in JPEG and MPEG-like coding standards. It is another object of this invention to provide an image transform which has overlapping basis functions so as to avoid blocking artifacts. It is a further object of this invention to provide a lapped transform which is approximately as fast as, but more efficient for compression than, the bare DCT. It is yet another object of this invention to provide dramatically improved speed and efficiency using a lapped transform with lifting steps in a butterfly structure with dyadic-rational coefficients. It is yet a further object of this invention to provide a transform structure such that for a negligible complexity surplus over the bare DCT a dramatic coding performance gain can be obtained both from a subjective and objective point of view while blocking artifacts are completely eliminated.